package algorithms.sort;

import algorithms.Util;

/**
 * 冒泡排序<br>
 * 升序<br>
 * 所谓冒泡是相邻元素对比，大的值往后冒泡。<br>
 * 每次从数组0开始扫描，将元素i与i+1对比，较大值存入i+1，较小值存入i，一次扫描完毕将扫描区间最大值冒泡到最后。<br>
 * 第i次扫描将[0,n-i-1]区间的最大值冒泡到n-i-1位置。<br>
 * 时间复杂度O(n^2)
 * 
 * @author shaoyuxia
 *
 * @param <T>
 */
public class BubbleSort<T extends Comparable<T>> implements ISort<T> {

	@Override
	public T[] sort(T[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 1; j < a.length - i; j++) {
				// 如果前一个元素大于后一个元素，就交换，把较大值冒上去
				if (a[j - 1].compareTo(a[j]) > 0) {
					Util.exchange(a, j - 1, j);
				}
			}
		}
		return a;
	}

}
